package com.pandy.code;

/**
 * @description: 单向链表练习题：找中间节点
 * @author: panhong
 * @date: 2025/3/26
 */
public class Code10_List_Midpoint {

    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 找中间节点
     * @param head
     * @return
     *      节点个数为奇数时返回中间节点
     *      节点个数为偶数时返回中间节点上一个节点
     */
    public static Node midpointOrUpMidpoint(Node head) {
        if(head == null || head.next == null || head.next.next == null) {
            return head;
        }

        // 链表至少有3个节点
        Node fast = head.next.next; // 快指针 每次走2步
        Node slow = head.next; // 慢指针 每次走1步
        Node next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 找中间节点
     * @param head
     * @return
     *      节点个数为奇数时返回中间节点
     *      节点个数为偶数时返回中间节点下一个节点
     */
    public static Node midpointOrDownMidpoint(Node head) {
        if(head == null || head.next == null) {
            return head;
        }

        // 链表至少有3个节点
        Node fast = head.next; // 快指针 每次走2步
        Node slow = head.next; // 慢指针 每次走1步
        Node next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        //node5.next = node6;

        Node midpointNode = midpointOrUpMidpoint(node1);
        System.out.println(midpointNode.value);

        Node midpointOrDownMidpoint = midpointOrDownMidpoint(node1);
        System.out.println(midpointOrDownMidpoint.value);
    }

}
